package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.book.BOfferS;
import pro.softzhang.algo.flag.knowledge.KBackTracking;
import pro.softzhang.algo.flag.theme.TMathCombination;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 *
 */
@BOfferS
@TMathCombination
public class LC40_CombinationSumII {
    public static void main(String[] args) {

    }

    /**
     *
     */
    @KBackTracking
    static
    class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> r = new LinkedList<>();
            LinkedList<Integer> c = new LinkedList<>();
            doCombinationSum2(candidates, target, 0, c, r);
            return r;
        }

        private void doCombinationSum2(int[] nums, int target, int i, LinkedList<Integer> c, List<List<Integer>> r) {
            if(target == 0) {
                r.add(new LinkedList<>(c));
                return;
            }

            if(target > 0 && i < nums.length) {
                doCombinationSum2(nums, target, getNext(nums, i), c, r);
                c.addLast(nums[i]);
                doCombinationSum2(nums, target - nums[i], i + 1, c, r);
                c.removeLast();
            }
        }

        private int getNext(int[] nums, int idx) {
            int next = idx;
            while (next < nums.length && nums[next] == nums[idx]) {
                next++;
            }
            return next;
        }
    }
}
